package book;

public class NumsLengthSolution {
    // 方法 1 直接求解——会发现执行时间比预期要慢很多
    static int getLength1(int n) {
        String s = "";
        for (int i = 1; i <= n; i++)
            s += i;
        return s.length();
    }

    // 方法 2 枚举+计算
    static int getLength2(int n) {
        int totalLength = 0;
        for (int i = 1; i <= n; i++) {
            int p = i, len = 1;
            while (p >= 10) {
                p /= 10;
                len += 1;
            }
            totalLength += len;
        }
        return totalLength;
    }

    // 方法 3 数学计算: 分别计算所有数字中个位、十位、百位……的总数，并加入到总和中
    // 时间复杂度：优化到O(lgN)
    static int getLength3(int n) {
        int totalLength = 0;
        int b = 1;
        while (n >= b) {
            totalLength += n - b + 1;
            b *= 10;
        }
        return totalLength;
    }

    public static void main(String[] args) {
        // System.out.print("请输入N: ");
        // Scanner scan = new Scanner(System.in);
        // int n = scan.nextInt();
        // scan.close();
        int n = 20000000;

        long t = System.currentTimeMillis();

        int method = 2, totalLength = 0;
        switch (method) {
            case 1:
                totalLength = getLength1(n);
                break;
            case 2:
                totalLength = getLength2(n);
                break;            
            case 3:
                totalLength = getLength3(n);
                break;                
        }

        t = System.currentTimeMillis() - t;

        System.out.println("使用方法" + method + " N=" + n + " 总长度为 " + totalLength);
        System.out.println("总时间：" + t + "毫秒");
    }
}

